FPS24 I - スコア

求めるものは$ \prod_{i=1}^n (1+A_ix) [x^k] である．

左辺の式を1つずつ掛け算していては計算量が$ O(N^2)\mathrm{polylog}(N) になって間に合わないが，次数が均等になるように上手く分割統治すると計算量が$ O(N\log^2 N)となり間に合う．今回はかける対象が全て1次式なので，セグ木の要領で半分ずつ計算すると間に合う．

積の和もFPSで扱える